👆 투 포인터 (Two Pointer)

투 포인터(Two Pointer) 는 배열이나 리스트에서 두 개의 포인터를 이용해 구간을 효율적으로 탐색하는 기법입니다.

보통 완전탐색 O(n²)을 O(n) 으로 줄일 때 사용됩니다.

1️⃣ 핵심 개념

"두 개의 인덱스를 이동시키며 조건을 만족하는 구간을 찾는다"

보통 이런 행태입니다:

[left ......... right]

• left: 구간의 시작
• right: 구간의 끝
• 현재 구간의 상태를 유지하면서 이동

2️⃣ 언제 사용하는가?

투 포이터는 보통 아래 조건에서 사용합니다.

🔥 대표 상황

• 연속 부분 수열의 합
• 특정 조건을 만족하는 최소 길이 구간
• 두 수의 합 문제 (정렬 배열)
• 슬라이딩 윈도우 문제

3️⃣ 기본 패턴

🔹 연속 구간 탐색

양의 정수로 이루어진 배열에서
합이 S 이상이 되는 가장 짧은 연속 부분 수열의 길이를 구하라.

🧠 아이디어

• right를 늘리면 합이 증가
• 합이 조건 이상이 되면 left를 줄여서 최소화

👉 구간을 "늘렸다 줄였다" 하며 조건을 맞춥니다.

💻 코드

function minSubArrayLength(nums, S) {
	let n = nums.length;
	let left = 0;
	let sum = 0;
	let minLen = Infinity;

	for (let right = 0; right < n; right++) {
		sum += nums[right];

		// 조건을 만족하면 줄일 수 있을 때까지 줄이기
		while (sum >= S) {
			minLen = Math.min(minLen, right - left + 1);
			sum -= nums[left];
			left++;
		}
	}

	return minLen === Infinity ? 0 : minLen;
}

console.log(minSubArrayLength([2,3,1,2,4,3], 7)); 
// ✅ 출력: 2  (부분 수열 [4,3])

🔹 정렬 배열에서 두 수의 합

정렬된 배열에서 합이 target이 되는 두 수를 찾기

🧠 아이디어

• left는 시작
• right는 끝
• 합이 작으면 left++
• 합이 크면 right--

👉 매번 탐색 범위를 절반이 아니라 "한 칸씩 줄이는 방식"

💻 코드

function twoSumSorted(nums, target) {
	let left = 0;
	let right = nums.length - 1;

	while (left < right) {
		let sum = nums[left] + nums[right];

		if (sum === target) {
			return [left, right];
		} 
		else if (sum < target) {
			left++;
		} 
		else {
			right--;
		}
	}

	return null;
}

console.log(twoSumSorted([1,2,3,4,6], 6));
// ✅ [1, 3]  (2 + 4)

5️⃣ 슬라이딩 윈도우와의 관계

투 포인터 중에서도

한 방향으로만 이동하는 구조

를 슬라이딩 윈도우라고 부릅니다.

right → 계속 증가
left → 필요할 때만 증가

대부분의 "연속 부분 수열 합" 문제는
👉 슬라이딩 윈도우입니다.

✍️ 한 줄 정리

투 포인터는 "두 인덱스를 이동시키며 구간을 효율적으로 줄여나가는 O(n) 탐색 기법"